package com.itheima.leetcode.od.b.violentenumeration;

import java.util.HashMap;

/**
 * (C卷,100分)- 水仙花数（Java & JS & Python & C）
 * <p>
 * 题目描述
 * <p>
 * 所谓水仙花数，是指一个n位的正整数，其各位数字的n次方和等于该数本身。
 * <p>
 * 例如153是水仙花数，153是一个3位数，并且153 = 1^3 + 5^3 + 3^3。
 * <p>
 * 输入描述
 * <p>
 * 第一行输入一个整数n，表示一个n位的正整数。n在3到7之间，包含3和7。
 * <p>
 * 第二行输入一个整数m，表示需要返回第m个水仙花数。
 * <p>
 * 输出描述
 * <p>
 * 返回长度是n的第m个水仙花数。个数从0开始编号。
 * <p>
 * 若m大于水仙花数的个数，返回最后一个水仙花数和m的乘积。
 * <p>
 * 若输入不合法，返回-1。
 * <p>
 * 用例
 * <p>
 * 输入
 * <p>
 * 3
 * <p>
 * 0
 * <p>
 * 输出	153
 * 说明	153是第一个水仙花数
 * <p>
 * 输入
 * <p>
 * 9
 * <p>
 * 1
 * <p>
 * 输出	-1
 * 说明	9超出范围
 * <p>
 * 题目解析
 * <p>
 * 这道题实现逻辑并不难，大家可以看下面算法源码。
 * <p>
 * 但是本题的水仙花数最长可以有7位，也就是百万级别的，虽然下面算法差不多是O(n)的，但是估计也Hold不住。
 * <p>
 * 暂时还没想到更好的办法。
 */
public class NarcissisticNumber {
    public static void main(String[] args) {
        /*Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int m = sc.nextInt();*/

        int n = 3;
        int m = 0;

        System.out.println(getResult(n, m));
    }

    public static long getResult(int n, int m) {
        // 若输入不合法，返回-1
        if (n < 3 || n > 7 || m < 0) {
            return -1;
        }

        // 提前计算好0~9的N次方, 避免后续进行重复计算
        HashMap<Character, Integer> powN = new HashMap<>();
        for (int i = 0; i <= 9; i++) {
            // 将整型0~9转化字符'0'~'9'，即让i+'0'即可
            powN.put((char) (i + '0'), (int) Math.pow(i, n));
        }

        // 最小的N位数
        int min = (int) Math.pow(10, n - 1);
        // 最大的N位数
        int max = (int) Math.pow(10, n);

        // 记录当前水仙花数
        long ans = 0;

        // 记录当前水仙花数是第几个
        int idx = 0;

        for (int num = min; num < max; num++) {
            // 记录num各位数字的N次方之和
            int sum = 0;

            // 遍历num的每一位数字
            String str = num + "";
            for (int i = 0; i < n; i++) {
                sum += powN.get(str.charAt(i));
            }

            // 判断num是否为水仙花数
            if (sum == num) {
                ans = num;
                // 如果num刚好是N位数的第m个水仙花数，则直接返回，否则继续查找
                if (idx++ == m) {
                    return ans;
                }
            }
        }

        // 若m大于水仙花数的个数，返回最后一个水仙花数和m的乘积
        return ans * m;
    }
}